﻿public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution
{
    public TreeNode DeleteNode(TreeNode root, int key)
    {
        // 找到要删除的节点
        TreeNode delNode = root, pre = null;
        while (delNode is not null)
        {
            if (delNode.val == key) break;

            pre = delNode;
            if (delNode.val > key) delNode = delNode.left;
            else delNode = delNode.right;
        }
        
        // 代替节点
        TreeNode newNode = delNode;
        if (delNode is null) return root;
        if (delNode.left is null && delNode.right is null) newNode = null;
        if (delNode.left is not null && delNode.right is null) newNode = delNode.left;
        if (delNode.right is not null && delNode.left is null) newNode = delNode.right;
        if (delNode.left is not null && delNode.right is not null)
        {
            newNode = delNode.right;
            TreeNode tempNode = newNode; // 辅助指针
            while (tempNode.left is not null)
            {
                tempNode = tempNode.left;
            }

            tempNode.left = delNode.left;
        }
        
        // 判断pre和delNode的关系
        if (pre is null) return newNode;
        else
        {
            bool isLeft = pre.right == delNode ? false : true;
            if (isLeft) pre.left = newNode;
            else pre.right = newNode;
        }
        
        return root;
    }

    public static void Main(string[] args)
    {
        int?[] root = [5, 3, 6, 2, 4, null, 7];
        int key = 3;

        TreeNode rootNode = CreatBinaryTree(root);

        Solution solution = new Solution();
        rootNode = solution.DeleteNode(rootNode, key);

        LevelOrderTraversa(rootNode);
    }

    private static void LevelOrderTraversa(TreeNode rootNode)
    {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        if (rootNode is not null) queue.Enqueue(rootNode);
        TreeNode node;

        while (queue.Count > 0)
        {
            node = queue.Dequeue();
            
            // 访问节点
            Console.Write($"{node.val} ");
            if (node.left is not null) queue.Enqueue(node.left);
            if (node.right is not null) queue.Enqueue(node.right);
        }
        
    }

    private static TreeNode CreatBinaryTree(int?[] root)
    {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        if (root is null || root.Length == 0 || root[0] is null) return null;
        
        // 根节点进队
        TreeNode rootNode = new TreeNode(root[0].Value);
        queue.Enqueue(rootNode);
        TreeNode node;
        int i = 1;
        bool flag;
        while (queue.Count > 0)
        {
            flag = true;
            // 出队
            node = queue.Dequeue();
            if (root[i] is not null)
            {
                flag = false;
                node.left = new TreeNode(root[i].Value);
                queue.Enqueue(node.left);
            }
            
            if (++i >= root.Length) break;
            if (root[i] is not null)
            {
                flag = false;
                node.right = new TreeNode(root[i].Value);
                queue.Enqueue(node.right);
            }

            if (++i >= root.Length) break;
            if (flag)
            {
                queue.Enqueue(node);
            }
        }

        return rootNode;
    }
}